The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for cache prefetching based on non-sequential lagging cache affinity.
A cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere. If requested data is contained in the cache (i.e., cache hit), this request can be served by simply reading the cache, which is comparatively faster. Otherwise (i.e., cache miss), the data must be recomputed or fetched from its original storage location, which is comparatively slower. Hence, the greater the number of requests that can be served from the cache, the faster the overall system performance becomes.
Small memories on or close to the CPU can operate faster than the much larger main memory. Web browsers and web proxy servers employ web caches to store previous responses from web servers, such as web pages and images. Web caches reduce the amount of information that needs to be transmitted across the network, as information previously stored in the cache can often be reused. This reduces bandwidth and processing requirements of the web server, and helps to improve responsiveness for users of the web. Database caching can substantially improve the throughput of database applications, for example in the processing of indexes, data dictionaries, and frequently used subsets of data.
Prefetching is the operation of loading data or instructions in anticipation of their need. There are known solutions for access patterns that are easily detectable, such as sequential prefetching. However, these solutions for access patterns are not able to take advantage of access patterns that appear random but are in fact frequently repeated sequences of events.